package algorithm.leetcode;

/**
 * @author wuwen
 * @since 2023/12/19
 */
public class NO300_最长递增子序列 {
    public static void main(String[] args) {

    }


    static class SolutionSelf {
        public int lengthOfLIS(int[] handles) {
            int answerMax = 1, size = handles.length;
            int[] dp = new int[size];
            dp[0] = 1;
            for (int i = 1; i < handles.length; i++) {
                dp[i] = 1;
                for (int j = 0; j < i; j++) {
                    if (handles[j] < handles[i]) {
                        dp[i] = Math.max(dp[i], dp[j]+1);
                    }
                }
                answerMax = Math.max(dp[i], answerMax);
            }
            return answerMax;
        }

    }

    static class Solution {
        /**
         * 使用DP的思想， 前一个子问题的解能否构造成功下一个问题的解。
         * 在加入下下一个数字的时候，其实已经知道了前面序列的增长序列大小
         * 所以问题变成了在加入第num[i]的数据时候，最长递增的子序列要么是加上当前的数据，形成新的，要么就是之前的num[i-1]所形成的最大递增子序列。
         */
        public int lengthOfLIS(int[] handles) {
            int size = handles.length;
            if (size == 0) {
                return 0;
            }
            int[] dp = new int[size];
            dp[0] = 0;
            int maxAns = 0;
            for (int i = 0; i < size; i++) {
                // 每一次默认只有自己是递增序列
                dp[i] = 1;
                // 从最开始到目前的位置再找一次
                for (int j = 0; j < i; j++) {
                    if (handles[j] < handles[i]) {
                        // 不断的循环来找出,之前匹配好的递增序列最大长度。
                        dp[i] = Math.max(dp[j] + 1, dp[i]);
                    }
                }
                maxAns = Math.max(maxAns, dp[i]);
            }
            return maxAns;
        }
    }
}
